Problem to reduce computational complexity from O(2^n)

The problem of reducing the amount of calculation from O(2^n) - Kenchon’s Competitive Pro Diligence Record []](https://drken1215.hatenablog.com/entry/20131222/1387706789)

• DP
  • Choices made in the present do not have a direct impact even into the distant future.
    • Sort n things in advance
  • knapsack problem
    • weighted-interval scheduling problem
  • simultaneous linear equations
  • https://archive.org/search.php?query=http%3A%2F%2Ftopcoder.g.hatena.ne.jp%2Fpepsin-amylase%2F20131203
  • rights-out system
  • minimum cut
  • maximal independent set problem
  • Patterns attributed to flow
    • Maximum Independent Set Problem on a Bipartite Graph
      • Number of vertices - Maximum matching of bipartite graphs
    • Maximum independent set problem on DAG satisfying transition rate - Equal to “DAG minimum path coverage” by [Dilworth’s theorem
    • Maximum Independent Set Problem on an Interval Graph - Interval Scheduling
  • Maximum independent set problem on a path
  • Maximum Independent Set Problem on a Tree
  • Maximal independent set problem on a directed tree with transitive closed envelopes
  • greedy algorithm
    • section scheduling problem
    • matroid
• shortest route problem
• least-cut problem

  • matroid crossing Problem

  • Given two matroids (E, F1), (E, F2), maximize at $F1\cap F2$. - Maximum matching of bipartite graphs Problem - the whole area of forested trees Problem - All Colorful Trees Issue.

    • The problem of packing a global tree

  • Introduction to Exponential Time Algorithms

---

This page is auto-translated from /nishio/O(2^n)から計算量を減らす問題 using DeepL. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I’m very happy to spread my thought to non-Japanese readers.